package leetcode.editor.cn;

//[5]最长回文子串

/**
 * @see arithmetic2.T_005_LongestPalindromicSubstring
 */
public class LongestPalindromicSubstring5 {
    public static void main(String[] args) {
        //int subLen = endIndex - beginIndex;
        String substring = "babad".substring(0, 1);//b .[) 前闭后开。因为。0 取到第一个值。len 取到最后一个值。len-1是最后一个index.
        System.out.println("LongestPalindromicSubstring5:main:" + substring);
        Solution solution = new LongestPalindromicSubstring5().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        //中间向两边扩张法 O(n^2)
        //执行耗时:17 ms,击败了84.89% 的Java用户
        public String longestPalindromeKuoSan(String s) {
            if (s == null || s.length() < 1) return null;
            int maxLen = 1;
            int startInd = 0;
            int endInd = 0;
            int len = s.length();

            for (int i = 0; i < len; i++) {
                //轴是字母 i
                int left = i - 1;
                int right = i + 1;
                while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                    int curlen = right - left + 1;
                    if (maxLen < curlen) {
                        maxLen = curlen;
                        startInd = left;
                        endInd = right;
                    }
                    left--;
                    right++;
                }

                //轴在 2 个字母中间。i i+1之间。
                int left2 = i;
                int right2 = i + 1;
                while (left2 >= 0 && right2 < len && s.charAt(left2) == s.charAt(right2)) {
                    int curLen = right2 - left2 + 1;
                    if (maxLen < curLen) {
                        maxLen = curLen;
                        startInd = left2;
                        endInd = right2;
                    }
                    left2--;
                    right2++;
                }

            }

            return s.substring(startInd, endInd + 1);//substring .前闭后开。 end-start = subLen.
        }


        //dp
        //执行耗时:159 ms,击败了34.23% 的Java用户
        //中心扩散的方法，其实做了很多重复计算。动态规划就是为了减少重复计算的问题。
        // 动态规划 空间换时间，将计算结果暂存起来，避免重复计算。
        //
        //初始状态，l=r 时，此时
        //状态转移方程：
        // if  r-l <=2 || dp[l+1][right-1]=true
        //    dp[l][r]=true
        // else
        //     dp[l][r]=false
        // r-l <=2 .
        // left right 1个字符 肯定是 true.
        // 2 个字符。且 相同肯定是 true
        // 3个字符。外面2个字符相同。肯定是true.
        //
        // 递推顺序：从 left--》right。for 2次 枚举所有的 dp[left][right] left<right.
        // 链接：https://leetcode.cn/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 1) return null;
            int len = s.length();
            int maxLen = 1;
            int startInd = 0;
            int endInd = 0;

            boolean[][] dp = new boolean[len][len];
            for (int right = 1; right < len; right++) {
                for (int left = 0; left < right; left++) {
                    if (s.charAt(left) == s.charAt(right)) {
                        if (right - left <= 2 || dp[left + 1][right - 1]) {
                            dp[left][right] = true;
                            int curLen = right - left + 1;
                            if (curLen > maxLen) {
                                maxLen = curLen;
                                startInd = left;
                                endInd = right;
                            }
                        } else {
                            dp[left][right] = false;
                        }
                    }
                }
            }

            return s.substring(startInd, endInd + 1);//substring .前闭后开。 end-start = subLen.
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}